package com.github.yangyishe.p100;

import java.util.ArrayList;
import java.util.List;

/**
 * 30. 串联所有单词的子串
 * https://leetcode.cn/problems/substring-with-concatenation-of-all-words/?envType=study-plan-v2&envId=top-interview-150
 * <p>
 * 给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
 * <p>
 * s 中的 串联子串 是指一个包含  words 中所有字符串以任意顺序排列连接起来的子串。
 * <p>
 * 例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。
 * 返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "barfoothefoobarman", words = ["foo","bar"]
 * 输出：[0,9]
 * 解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
 * 子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
 * 子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
 * 输出顺序无关紧要。返回 [9,0] 也是可以的。
 * 示例 2：
 * <p>
 * 输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
 * 输出：[]
 * 解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
 * s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
 * 所以我们返回一个空数组。
 * 示例 3：
 * <p>
 * 输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
 * 输出：[6,9,12]
 * 解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。
 * 子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。
 * 子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。
 * 子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= s.length <= 104
 * 1 <= words.length <= 5000
 * 1 <= words[i].length <= 30
 * words[i] 和 s 由小写英文字母组成
 */
public class Problem30 {
    public static void main(String[] args) {
//        System.out.println(0b1001^0b1101);
        String s = "ababaab";
        String[] words = new String[]{"ab", "ba", "ba"};

        Problem30 problem30 = new Problem30();
        List<Integer> substring = problem30.findSubstring(s, words);
        System.out.println(substring);

    }

    private final long[] charHash = new long[26];

    /**
     * 思路1:暴力破解
     * 1. 寻找words[0]在s中的第一个索引
     * 2. 分别在当前索引前后, 寻找符合words其他字符串的情况.
     * 2.1. 如果有, 则在现有基础上继续寻找
     * 2.2. 如果没有, 则在已寻找的字符串基础上, 寻找下一个索引
     * <p>
     * 思路2:唯一数字法.
     * 给每一个字符一个独一无二的数字,如任意一个对象的hash值.
     * 对于一个word,使用sigma(i*hash)的方法, 获取独一无二的数字
     * 而一个words, 取其和, 及所有word的唯一值之和
     * <p>
     * <p>
     * 对于一个字符串, 首先对每一位数字获取其唯一值,
     * 接着, 求取每一位包含其后wordLen长度的唯一值.
     * 最后, 每隔wordsSize长度, 求取其汇总唯一值之和.
     * 长度与要求sumLen相等的, 即为要求索引.
     * <p>
     * 时间复杂度O(n)
     * <p>
     * 缺陷修复:
     * 1. 无法识别["ab","ba"]和["aa","bb"]两种情况
     * 解决: 给"ab"和"ba"一个独一无二数字offset. 以与"aa"和"bb"区分开.
     * 如考虑二次哈希. 譬如对每个除了a+2b外, 在加上关联因子(不能用加法).
     *
     * @param s
     * @param words
     * @return
     */
    public List<Integer> findSubstring(String s, String[] words) {
        for (int i = 0; i < 26; i++) {
            charHash[i] = new Object().hashCode();
        }

        int wordLen = words[0].length();
//        long[] wordHashArr = new long[words.length];
        long wordHashSum = 0;
        for (int i = 0; i < words.length; i++) {
            long wordHash = calcWordHash(words[i]);
//            wordHashArr[i] = wordHash;
            wordHashSum += wordHash;
        }

        long[] strHashArr = new long[s.length()];
        for (int i = 0; i < s.length(); i++) {
            strHashArr[i] = charHash[s.charAt(i) - 'a'];
        }

        long[] strWordHashArr = new long[s.length() - wordLen + 1];
        for (int i = 0; i < s.length() - wordLen + 1; i++) {
            long wordHash = calcWordHash(strHashArr, i, wordLen);
//            for(int j=0;j< wordLen;j++){
//                wordHash+=(strHashArr[i+j])<<j;
//            }
            strWordHashArr[i] = wordHash;
        }
        long[] strWordsHashArr = new long[s.length() - wordLen * words.length + 1];
        for (int i = 0; i <= s.length() - wordLen * words.length; i++) {
            for (int j = 0; j < words.length; j++) {
                strWordsHashArr[i] += strWordHashArr[i + wordLen * j];
            }
        }

        List<Integer> resultList = new ArrayList<>();
        for (int i = 0; i < strWordsHashArr.length; i++) {
            if (strWordsHashArr[i] == wordHashSum) {
                resultList.add(i);
            }
        }


        return resultList;
    }

    private long calcWordHash(String word) {
        long wordHash = 0;
        for (int j = 0; j < word.length(); j++) {
            wordHash += (charHash[word.charAt(j) - 'a'] +
                    (j + 1 != word.length() ?
                            (charHash[word.charAt(j) - 'a'] ^
                                    charHash[word.charAt(j + 1) - 'a']) : 0)
            ) << j;
        }
        return wordHash;
    }

    private long calcWordHash(long[] hashArr, int startIndex, int wordLen) {
        long wordHash = 0;
        for (int j = 0; j < wordLen; j++) {
            wordHash += (hashArr[startIndex + j] +
                    (j + 1 != wordLen ?
                            (hashArr[startIndex + j] ^
                                    hashArr[startIndex + j + 1]) : 0)
            ) << j;
        }
        return wordHash;
    }


}
